package LeetCode._01_树;

import javax.swing.tree.TreeNode;

public class _99_恢复二叉搜索树 {
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
    }

    TreeNode first = null,second = null;
    TreeNode pre = new TreeNode(Integer.MIN_VALUE); //判断中序遍历的有效性
    public void recoverTree(TreeNode root) {
        inorderTraverse(root);

        int temp = first.val;;
        first.val = second.val;
        second.val = temp;
    }

    private void inorderTraverse(TreeNode root){
        if(root == null) return;
        inorderTraverse(root.left);

        if(root.val < pre.val){ //遍历到每一个节点，当前节点小于上一个节点，破化了有效性
            if(first == null){
                //第一个错误的节点
                first = pre;
            }
            //第二个错误的节点
            second = root;
        }
        pre = root; //更新上一个节点，对于下次遍历
        inorderTraverse(root.right);
    }
}
